1017. 负二进制转换【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟进制转换

1. 📝 题目描述

• leetcode

给你一个整数 n，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。

注意， 除非字符串就是 "0"，否则返回的字符串中不能含有前导零。

---

示例 1：

输入：n = 2
输出："110"
解释：(-2)2 + (-2)1 = 2

示例 2：

输入：n = 3
输出："111"
解释：(-2)2 + (-2)1 + (-2)0 = 3

示例 3：

输入：n = 4
输出："100"
解释：(-2)2 = 4

---

提示：

• 0 <= n <= 10^9

2. 🎯 s.1 - 模拟进制转换

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number} n
 * @return {string}
 */
var baseNeg2 = function (n) {
  if (n === 0) return '0'
  let res = ''
  while (n !== 0) {
    const remainder = n & 1
    res = remainder + res
    n = (n - remainder) / -2
  }
  return res
}

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(\log n)$，存储结果字符串

算法思路：

• 类似普通进制转换，每次取 n & 1 作为当前位，然后 n = (n - remainder) / -2
• 由于基数为 -2，余数始终为 0 或 1，得到的每一位都是合法的二进制位